package com.ryujung.hash.leetCode_242;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {

    // 优化map存放的方式
    public boolean isAnagram(String s, String t) {
        if (s == null || t == null) return s == t;
        if (s.length() != t.length()) return false;

        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        Arrays.sort(sc);
        Arrays.sort(tc);
        for (int i = 0; i < s.length(); i++) {
            if (sc[i] != tc[i]) return false;
        }
        return true;
    }
    // 时间复杂度：O(nlogn)
    // 空间复杂度：O(logn)

    /**
     * 使用map存放每个（char，出现次数）的键值对，然后对比两个string中的char个数
     * 时间复杂度：O(n+m) 遍历两个字符串中的所有字符，m、n为字符数量
     * 空间复杂度: O(n) 需要存放不同字符的键值对，对话情况为 n
     */
    public boolean isAnagram11(String s, String t) {
        if (t == null || s == null) return s == t;
        if (t.length() != s.length()) return false;

        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (char c : s.toCharArray()) {
            if (map.get(c) == null) {
                return false;
            }
            map.put(c, map.get(c) - 1);
        }
        for (Integer value : map.values()) {
            if (value != 0) {
                return false;
            }
        }
        return true;
    }
    // 时间复杂度：O(n)
    // 空间复杂度：O(S) map的大小，取决于字符集的大小，这里是26

}